package two.chapter_1.c1_4;

public class BinarySearch {

    /**
     * 二分查找   logN
     * @param key
     * @param a
     * @return
     */
    public static int rank(int key,int[]a){
        return rank(key,0,a.length-1,a);
    }

    public static int rank(int key, int lo, int hi, int[] a) {

        while (lo<=hi){
            int mid=lo+(hi-lo)/2;
            int cmp=key-a[mid];
            if (cmp>0){
                lo=mid+1;
            }else if (cmp==0){
                return mid;
            }else {
                hi=mid-1;
            }

        }
        return -1;
    }

    /**
     * 返回和key相等的最小的index
     * @param key
     * @param lo
     * @param hi
     * @param a
     * @return
     */
    public static int rankMin(int key, int lo, int hi, int[] a){
        int min=-1;
        while (lo<=hi){
            int mid=lo+(hi-lo)/2;
            int cmp=key-a[mid];
            if (cmp>0){
                lo=mid+1;
            }else if (cmp==0){
                hi=mid-1;
                if (hi<0 ||a[hi]<key){
                    return mid;
                }
                min=mid;
                //if ()
                //return mid;
            }else {
                hi=mid-1;
            }

        }
        return min;
    }

    /**
     * 返回和key相等的最大的index
     * @param key
     * @param lo
     * @param hi
     * @param a
     * @return
     */
    public static int rankMax(int key, int lo, int hi, int[] a){
        int max=-1;
        while (lo<=hi){
            int mid=lo+(hi-lo)/2;
            int cmp=key-a[mid];
            if (cmp>0){
                lo=mid+1;
            }else if (cmp==0){
                lo=mid+1;
                if (lo>hi ||a[lo]>key){
                    return mid;
                }
                max=mid;
                //if ()
                //return mid;
            }else {
                hi=mid-1;
            }

        }
        return max;
    }
}
